//只有满足下面几点之一，括号字符串才是有效的：
//
//
// 它是一个空字符串，或者
// 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
// 它可以被写作 (A)，其中 A 是有效字符串。
//
//
// 给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。
//
//
// 例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。
//
//
// 返回 为使结果字符串 s 有效而必须添加的最少括号数。
//
//
//
// 示例 1：
//
//
//输入：s = "())"
//输出：1
//
//
// 示例 2：
//
//
//输入：s = "((("
//输出：3
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 只包含 '(' 和 ')' 字符。
//
// Related Topics栈 | 贪心 | 字符串
//
// 👍 149, 👎 0
//
//
//
//

package leetcode.editor.day;

class MinimumAddToMakeParenthesesValid {
    public static void main(String[] args) {
        Solution solution = new MinimumAddToMakeParenthesesValid().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://labuladong.gitee.io/algo/4/33/130/
        /*public int minAddToMakeValid(String s) {
            int res = 0;  // 左括号的插入个数
            int need = 0; // 需要多少右括号

            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    // 右括号需求加一
                    need++;
                }

                if (s.charAt(i) == ')') {
                    // 对右括号的需求 - 1
                    need--;

                    if (need < 0) {
                        need = 0;
                        // 右括号过多，需要插入一个左括号
                        res++;
                    }
                }

            }

            return res + need;
        }*/

        public int minAddToMakeValid(String s) {
            // 需要匹配的左右括号数
            int lCnt = 0, rCnt = 0;
            for (char c : s.toCharArray()) {
                // 遇到左括号，必须要一个右括号来匹配
                // 因为左括号在前，右括号在后，所以前面出现右括号也无法使用本次左括号来匹配
                if (c == '(') {
                    rCnt++;
                }

                // 遇到右括号，如果前面需要右括号匹配，那可以抵消，如果前面没有左括号匹配，那需要一个左括号
                if (c == ')') {
                    if (rCnt > 0) rCnt--;
                    else lCnt++;
                }
            }

            // 结果是左括号加上右括号
            return lCnt + rCnt;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
